package leetcode.graph.hamilton.p980;

import java.util.Arrays;

/**
 * 
 * @Title: Solution.java 
 * @Package leetcode.graph.hamilton 
 * @Description: 980. 不同路径 III
 *                   自己的题解：不压缩二维数组的索引
 *                       改进：1、优化递归方法中的条件判断，避免重复判断二维数组的索引是否合法
 *                           2、基于v5进一步状态压缩
 *                             根据题意，1 <= grid.length * grid[0].length <= 20，
 *                             数据规模比较小，一个int型数字占4个字节，总共32位，20是小于32的，
 *                             并且visited数组中的每一个元素是boolean型的，表示true和false两种状态，而
 *                             二进制数的每一位上有0和1两种状态，正好可以和false和true对应起来
 *                             因此，可以把visited数组压缩成一个int型数字，然后用位运算替换访问、修改等操作。\
 *                           3、基于v6将visited作为dfs方法的参数传入
 *                           4、基于v7添加记忆化搜索（缓存），避免重复搜索
 * @author CandyWall   
 * @date 2021年1月19日 下午1:05:22 
 * @version V1.0
 */
class Solution_v8 {
    private int R;
    private int C;
    private int[][] grid;
    private int[][] dirs = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};
    private int[][] memo;
    public int uniquePathsIII(int[][] grid) {
        this.grid = grid;
        R = grid.length;
        C = grid[0].length;
        int visited = 0;    // 转成二进制以后32位都是0，表示顶点都没有被访问
        // 初始化缓存数组
        memo = new int[1 << R * C][R * C];
        for(int i = 0; i < memo.length; i++) {
            Arrays.fill(memo[i], -1);
        }
        // 找出起始位置，并且统计空方格的个数
        int blank_count = 0;
        int firstI = 0;
        int firstJ = 0;
        for(int i = 0; i < R; i++) {
            for(int j = 0; j < C; j++) {
                if(grid[i][j] == 1) {
                    firstI = i;
                    firstJ = j;
                } else if(grid[i][j] == 0) {
                    blank_count++;
                }
            }
        }
        // 起始方格也需要加入到未遍历的定点数中
        // 如果把递归终止条件放到循环里面（会少一次递归调用，left少减一次），
        // 最后的那个结束方格代表的顶点就不能算作未遍历的顶点
        // 因此只把起始方格加在里面，而不能算结束方格
        return dfs(visited, firstI, firstJ, blank_count + 1);
    }
    
    private int dfs(int visited, int i, int j, int left) {
        int v = i * C + j;
        if(memo[visited][v] != -1) {
            return memo[visited][v];
        }
        int count = 0;
        left--;
        // 将二进制中的某一位改为1
        visited += (1 << v);
        for(int d = 0; d < 4; d++) {
            int nextI = dirs[d][0] + i;
            int nextJ = dirs[d][1] + j;
            if(inArea(nextI, nextJ)) {
                int w = nextI * C + nextJ;
                if((visited & (1 << w)) == 0 && grid[nextI][nextJ] == 0) {
                    count += dfs(visited, nextI, nextJ, left);
                }
                // 如果把递归终止条件放到循环里面，最后的那个结束方格代表的顶点就不能算作未遍历的顶点
                else if(left == 0 && grid[nextI][nextJ] == 2) {
                    // visited -= (1 << v);
                    memo[visited][v] = 1;
                    return 1;
                }
            } 
        }
        
        // visited作为了方法的参数，因此完成本次调用不需要复位，
        // 对当前visited的修改不会对上层递归调用中的visited产生影响
        // visited -= (1 << v);
        memo[visited][v] = count;
        return count;
    }
    
    // 判断二维数组的索引是否合法
    private boolean inArea(int x, int y) {
        return x >= 0 && x < R && y >= 0 && y < C;
    }
    
    public static void main(String[] args) {
        System.out.println(new Solution_v8().uniquePathsIII(new int[][] {{1,0,0,0}, {0,0,0,0}, {0,0,2,-1}}));
    }
}